package com.gorkr;

import org.junit.jupiter.api.Test;

/**
 * @author gorkr
 * @date 2022/01/14 22:43
 * 前序遍历和中序遍历序列 构造二叉树
 **/


public class L7 {
    int index = 0;


    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return traverse(preorder,inorder,0,inorder.length-1);

    }

    public TreeNode traverse(int[] preorder, int[] inorder, int start, int end) {

        if(start>end || index>=inorder.length){
            return null;
        }
//        if(start==end){
//            return new TreeNode(inorder[start]);
//        }

        // 根节点
        TreeNode root = new TreeNode(preorder[index]);

        int mid=start;
        for (; mid<= end; mid++) {
            if(inorder[mid]==root.val){
                break;
            }
        }


        index++;
        root.left = traverse(preorder,inorder,start,mid-1);
        root.right = traverse(preorder,inorder,mid+1,end);

        return root;
    }

    @Test
    public void test(){
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        buildTree(preorder,inorder);
    }

}
    